class Solution {//leetcode493——翻转对
private:
    int merge_sort(vector<int>& nums,int begin,int end){
        if(begin>=end) return 0;
        //分治
        int mid=(end+begin)/2;
        int a=merge_sort(nums,begin,mid);
        int b=merge_sort(nums,mid+1,end);
        int c=0;

        //计算两个降序数组的翻转对个数
        for(int left=begin,right=mid+1;left<=mid&&right<=end;){
            if(nums[left]<=(long long)nums[right]*2) right++;
            else{// if nums[left]>nums[right]*2
                c+=end-right+1;
                left++;
            }
        }

        //将两个降序子数组归并成新的降序子数组
        int cur1=begin,cur2=mid+1,i=begin;
        while(cur1<=mid&&cur2<=end){
            if(nums[cur1]>nums[cur2]) tmp[i++]=nums[cur1++];
            else tmp[i++]=nums[cur2++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=end) tmp[i++]=nums[cur2++];

        for(int j=begin;j<=end;j++) nums[j]=tmp[j];

        return a+b+c;
    }
public:
    int reversePairs(vector<int>& nums) {
        int n=nums.size();
        tmp.resize(n);
        return merge_sort(nums,0,n-1);
    }
private:
    vector<int> tmp;
};